#include <lua.h>

#include <lauxlib.h>

#include <lualib.h>

#include <time.h>
#include <math.h>
#include <float.h>

#define FIGS	l_mathlim(MANT_DIG)

#if FIGS > 64
#undef FIGS
#define FIGS 64
#endif

/*
** LUA_RAND32 forces the use of 32-bit integers in the implementation
** of the PRN generator (mainly for testing).
*/
#if !defined(LUA_RAND32) && !defined(Rand64)

/* try to find an integer type with at least 64 bits */

#if (LONG_MAX >> 31 >> 31) >= 1

/* 'long' has at least 64 bits */
#define Rand64		unsigned long

#elif !defined(LUA_USE_C89) && defined(LLONG_MAX)

/* there is a 'long long' type (which must have at least 64 bits) */
#define Rand64		unsigned long long

#elif (LUA_MAXINTEGER >> 31 >> 31) >= 1

/* 'lua_Integer' has at least 64 bits */
#define Rand64		lua_Unsigned

#endif

#endif


#if defined(Rand64)  /* { */

/*
** Standard implementation, using 64-bit integers.
** If 'Rand64' has more than 64 bits, the extra bits do not interfere
** with the 64 initial bits, except in a right shift. Moreover, the
** final result has to discard the extra bits.
*/

/* avoid using extra bits when needed */
#define trim64(x)	((x) & 0xffffffffffffffffu)


/* rotate left 'x' by 'n' bits */
static Rand64 rotl (Rand64 x, int n) {
	return (x << n) | (trim64(x) >> (64 - n)); 
}

static Rand64 nextrand (Rand64 *state) {
	Rand64 state0 = state[0];
	Rand64 state1 = state[1];
	Rand64 state2 = state[2] ^ state0;
	Rand64 state3 = state[3] ^ state1;
	Rand64 res = rotl(state1 * 5, 7) * 9;
	state[0] = state0 ^ state3;
	state[1] = state1 ^ state2;
	state[2] = state2 ^ (state1 << 17);
	state[3] = rotl(state3, 45);
	return res;
}


/* must take care to not shift stuff by more than 63 slots */


/*
** Convert bits from a random integer into a float in the
** interval [0,1).
*/
#define maskFIG		(~(~(Rand64)1 << (FIGS - 1)))  /* use FIGS bits */
#define shiftFIG  \
	(l_mathop(0.5) / ((Rand64)1 << (FIGS - 1)))  /* 2^(-FIGS) */

static lua_Number I2d (Rand64 x) {
	return (lua_Number)(x & maskFIG) * shiftFIG;
}

/* convert a 'Rand64' to a 'lua_Unsigned' */
#define I2UInt(x)	((lua_Unsigned)trim64(x))

/* convert a 'lua_Unsigned' to a 'Rand64' */
#define Int2I(x)	((Rand64)(x))


#else	/* no 'Rand64'   }{ */

/* get an integer with at least 32 bits */
#if (INT_MAX >> 30) >= 1
typedef unsigned int lu_int32;
#else
typedef unsigned long lu_int32;
#endif


/*
** Use two 32-bit integers to represent a 64-bit quantity.
*/
typedef struct Rand64 {
	lu_int32 h;  /* higher half */
	lu_int32 l;  /* lower half */
} Rand64;


/*
** If 'lu_int32' has more than 32 bits, the extra bits do not interfere
** with the 32 initial bits, except in a right shift and comparisons.
** Moreover, the final result has to discard the extra bits.
*/

/* avoid using extra bits when needed */
#define trim32(x)	((x) & 0xffffffffu)


/*
** basic operations on 'Rand64' values
*/

/* build a new Rand64 value */
static Rand64 packI (lu_int32 h, lu_int32 l) {
	Rand64 result;
	result.h = h;
	result.l = l;
	return result;
}

/* return i << n */
static Rand64 Ishl (Rand64 i, int n) {
	lua_assert(n > 0 && n < 32);
	return packI((i.h << n) | (trim32(i.l) >> (32 - n)), i.l << n);
}

/* i1 ^= i2 */
static void Ixor (Rand64 *i1, Rand64 i2) {
	i1->h ^= i2.h;
	i1->l ^= i2.l;
}

/* return i1 + i2 */
static Rand64 Iadd (Rand64 i1, Rand64 i2) {
	Rand64 result = packI(i1.h + i2.h, i1.l + i2.l);
	if (trim32(result.l) < trim32(i1.l))  /* carry? */
	result.h++;
	return result;
}

/* return i * 5 */
static Rand64 times5 (Rand64 i) {
	return Iadd(Ishl(i, 2), i);  /* i * 5 == (i << 2) + i */
}

/* return i * 9 */
static Rand64 times9 (Rand64 i) {
	return Iadd(Ishl(i, 3), i);  /* i * 9 == (i << 3) + i */
}

/* return 'i' rotated left 'n' bits */
static Rand64 rotl (Rand64 i, int n) {
	lua_assert(n > 0 && n < 32);
	return packI((i.h << n) | (trim32(i.l) >> (32 - n)),
				 (trim32(i.h) >> (32 - n)) | (i.l << n));
}

/* for offsets larger than 32, rotate right by 64 - offset */
static Rand64 rotl1 (Rand64 i, int n) {
	lua_assert(n > 32 && n < 64);
	n = 64 - n;
	return packI((trim32(i.h) >> n) | (i.l << (32 - n)),
				 (i.h << (32 - n)) | (trim32(i.l) >> n));
}

/*
** implementation of 'xoshiro256**' algorithm on 'Rand64' values
*/
static Rand64 nextrand (Rand64 *state) {
	Rand64 res = times9(rotl(times5(state[1]), 7));
	Rand64 t = Ishl(state[1], 17);
	Ixor(&state[2], state[0]);
	Ixor(&state[3], state[1]);
	Ixor(&state[1], state[2]);
	Ixor(&state[0], state[3]);
	Ixor(&state[2], t);
	state[3] = rotl1(state[3], 45);
	return res;
}


/*
** Converts a 'Rand64' into a float.
*/

/* an unsigned 1 with proper type */
#define UONE		((lu_int32)1)

#if FIGS <= 32

#define maskHI		0  /* do not need bits from higher half */
#define maskLOW		(~(~UONE << (FIGS - 1)))  /* use FIGS bits */
#define shiftFIG	(l_mathop(0.5) / (UONE << (FIGS - 1)))  /* 2^(-FIGS) */

#else	/* 32 < FIGS <= 64 */

/* must take care to not shift stuff by more than 31 slots */

/* use FIGS - 32 bits from higher half */
#define maskHI		(~(~UONE << (FIGS - 33)))

/* use 32 bits from lower half */
#define maskLOW		(~(~UONE << 31))

/* 2^(-FIGS) == (1 / 2^33) / 2^(FIGS-33) */
#define shiftFIG  ((lua_Number)(1.0 / 8589934592.0) / (UONE << (FIGS - 33)))

#endif

#define twoto32		l_mathop(4294967296.0)  /* 2^32 */

static lua_Number I2d (Rand64 x) {
	lua_Number h = (lua_Number)(x.h & maskHI);
	lua_Number l = (lua_Number)(x.l & maskLOW);
	return (h * twoto32 + l) * shiftFIG;
}


/* convert a 'Rand64' to a 'lua_Unsigned' */
static lua_Unsigned I2UInt (Rand64 x) {
	return ((lua_Unsigned)trim32(x.h) << 31 << 1) | (lua_Unsigned)trim32(x.l);
}

/* convert a 'lua_Unsigned' to a 'Rand64' */
static Rand64 Int2I (lua_Unsigned n) {
	return packI((lu_int32)(n >> 31 >> 1), (lu_int32)n);
}

#endif  /* } */


/*
** A state uses four 'Rand64' values.
*/
typedef struct {
	Rand64 s[4];
} RanState;


/*
** Project the random integer 'ran' into the interval [0, n].
** Because 'ran' has 2^B possible values, the projection can only be
** uniform when the size of the interval is a power of 2 (exact
** division).  To get a uniform projection into [0, n], we first compute
** 'lim', the smallest Mersenne number not smaller than 'n'. We then
** project 'ran' into the interval [0, lim].  If the result is inside
** [0, n], we are done. Otherwise, we try with another 'ran', until we
** have a result inside the interval.
*/
static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n,
							 RanState *state) {
	lua_Unsigned lim = n;
	if ((lim & (lim + 1)) > 0) {  /* 'lim + 1' is not a power of 2? */
	/* compute the smallest (2^b - 1) not smaller than 'n' */
	lim |= (lim >> 1);
	lim |= (lim >> 2);
	lim |= (lim >> 4);
	lim |= (lim >> 8);
	lim |= (lim >> 16);
#if (LUA_MAXINTEGER >> 30 >> 1) > 0
	lim |= (lim >> 32);  /* integer type has more than 32 bits */
#endif
	}
	lua_assert((lim & (lim + 1)) == 0  /* 'lim + 1' is a power of 2, */
	&& lim >= n  /* not smaller than 'n', */
	&& (lim == 0 || (lim >> 1) < n));  /* and it is the smallest one */
	while ((ran &= lim) > n)  /* project 'ran' into [0..lim] */
	ran = I2UInt(nextrand(state->s));  /* not inside [0..n]? try again */
	return ran;
}


static inline RanState *
get_userdata(lua_State *L) {
	return lua_touserdata(L, lua_upvalueindex(1));
}


static int
math_random (lua_State *L) {
	lua_Integer low, up;
	lua_Unsigned p;
	RanState *state = get_userdata(L);
	Rand64 rv = nextrand(state->s);  /* next pseudo-random value */
	switch (lua_gettop(L)) {  /* check number of arguments */
	case 0: {  /* no arguments */
		lua_pushnumber(L, I2d(rv));  /* float between 0 and 1 */
		return 1;
	}
	case 1: {  /* only upper limit */
		low = 1;
		up = luaL_checkinteger(L, 1);
		if (up == 0) {  /* single 0 as argument? */
		lua_pushinteger(L, I2UInt(rv));  /* full random integer */
		return 1;
		}
		break;
	}
	case 2: {  /* lower and upper limits */
		low = luaL_checkinteger(L, 1);
		up = luaL_checkinteger(L, 2);
		break;
	}
	default: return luaL_error(L, "wrong number of arguments");
	}
	/* random integer in the interval [low, up] */
	luaL_argcheck(L, low <= up, 1, "interval is empty");
	/* project random integer into the interval [0, up - low] */
	p = project(I2UInt(rv), (lua_Unsigned)up - (lua_Unsigned)low, state);
	lua_pushinteger(L, p + (lua_Unsigned)low);
	return 1;
}


static void
setseed (Rand64 *state, lua_Unsigned n1, lua_Unsigned n2) {
	int i;
	state[0] = Int2I(n1);
	state[1] = Int2I(0xff);  /* avoid a zero state */
	state[2] = Int2I(n2);
	state[3] = Int2I(0);
	for (i = 0; i < 16; i++)
	nextrand(state);  /* discard initial values to "spread" seed */
}


static int
math_randomseed (lua_State *L) {
	RanState *state = get_userdata(L);
	lua_Integer n1 = luaL_checkinteger(L, 1);
	lua_Integer n2 = luaL_optinteger(L, 2, 0);
	setseed(state->s, n1, n2);
	return 0;
}


static const luaL_Reg randfuncs[] = {
	{"random", math_random},
	{"randomseed", math_randomseed},
	{NULL, NULL},
};


int
luaopen_rand54_c(lua_State *L) {
	luaL_newlibtable(L, randfuncs);
	RanState *state = (RanState*)lua_newuserdata(L, sizeof(RanState));
	lua_Unsigned seed1 = (lua_Unsigned)time(NULL); 
	lua_Unsigned seed2 = (lua_Unsigned)(size_t)L; 
	setseed(state->s, seed1, seed2);
	luaL_setfuncs(L, randfuncs, 1);
	return 1;
}
